Leetcode92 反转链表(反转指定位置的链表) |
您所在的位置:网站首页 › 反转从位置 m 到 n 的链表 › Leetcode92 反转链表(反转指定位置的链表) |
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
反转链表普通做法头插法(一次遍历)
反转链表普通做法
1 -> 3 -> 2 -> 4 -> 5 -> NULL 1 -> 4 -> 3 -> 2 -> 5 -> NULL 我们可以看出来,总共需要n-m步即可,第一步是将结点3放到结点1的后面,第二步将结点4放到结点1的后面。这是很有规律的操作,那么我们就说一个就行了,比如刚开始,pre指向结点1,cur指向结点2,然后我们建立一个临时的结点t,指向结点3(注意我们用临时变量保存某个结点就是为了首先断开该结点和前面结点之间的联系,这可以当作一个规律记下来),然后我们断开结点2和结点3,将结点2的next连到结点4上,也就是 cur->next = t->next,再把结点3连到结点1的后面结点(即结点2)的前面,即 t->next = pre->next,最后再将原来的结点1和结点2的连接断开,将结点1连到结点3,即 pre->next = t。这样我们就完成了将结点3取出,加入结点1的后方。第二步将结点4取出,加入结点1的后方,也是同样的操作, |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |